package dataStructBinaryTree;

import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TestLeeCoNiuKe {

    class TreeNode{
        int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;

        public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null || p != null && q == null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        boolean left = isSameTree(p.left,q.left);
        boolean right = isSameTree(p.right,q.right);
        return left && right ;
        }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if (root == null || subRoot == null){
                return false;
            }
            if (isSameTree(root,subRoot)) return true;
            if (isSameTree(root.left,subRoot)) return true;
            if (isSameTree(root.right,subRoot)) return true;
            return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    public boolean isBalanced(TreeNode root) {
        return getHight(root)>=0;
    }

    public int getHight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHight(root.left);
        int right = getHight(root.right);
        if(left >= 0 && right >=0 &&
                Math.abs(left-right)<2){
            return Math.max(left,right)+1;
        }else {
            return -1;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return false;
        }
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode rootLeft,TreeNode rootRight){
            if(rootLeft == null && rootRight != null || rootLeft != null && rootRight == null ){
                return false;
            }
            if (rootLeft == null && rootRight == null){
                return true;
            }
            if(rootLeft.val != rootRight.val){
                return false;
            }
            return isSymmetricChild(rootLeft.left,rootRight.right) && isSymmetricChild(rootLeft.right,rootRight.left);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while (size > 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }

//        public void merge(int[] nums1, int m, int[] nums2, int n) {
//            int[] tmp = new int[m + n];
//            int cur = 0;
//            if(m == 0){
//                for (int k = 0; k < m+n; k++) {
//                    nums1[k] = nums2[k];
//                }
//            }
//            int i,j;
//            for ( i = 0,j = 0; i < m && j < n; ) {
//                if(nums1[i] <= nums2[j]){
//                    tmp[cur] = nums1[i];
//                    cur++;
//                    i++;
//                }else {
//                    tmp[cur] = nums2[j];
//                    cur++;
//                    j++;
//                }
//            }
//            if(!(j<n) ){
//                for (int k = i; k < m; k++) {
//                    tmp[cur] = nums1[k];
//                    cur++;
//                }
//            }
//            if(!(i<m)){
//                for (int k = j; k < n; k++) {
//                    tmp[cur] = nums2[k];
//                    cur++;
//                }
//            }
//            for (int k = 0; k < m+n; k++) {
//                nums1[k] = tmp[k];
//            }
//        }

//        public int removeDuplicates(int[] nums) {
//            int fast = 1;
//            int slow = 0;
//            while (fast < nums.length) {
//                if (nums[slow] != nums[fast]) {
//                    nums[++slow] = nums[fast];
//                }
//                fast++;
//            }
//            return slow + 1;
//        }
//
//
//        class TreeNode1{
//            public char val;
//            public TreeNode1 left;
//            public TreeNode1 right;
//            public TreeNode1(char val){
//                this.val = val;
//            }
//        }
//
//
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextLine()) { // 注意 while 处理多个 case
//                String str = in.nextLine();
//                TreeNode root = creatTree(str);
//                soutTree(root);
//            }
//        }
//
//        public static int i = 0;
//
//        public static TreeNode creatTree(String str) {
//            TreeNode root = null;
//            if (str.charAt(i) != '#') {
//                root = new TreeNode(str.charAt(i));
//                i++;
//                root.left = creatTree(str);
//                root.right = creatTree(str);
//            } else {
//                i++;
//            }
//            return root;
//        }
//
//        public static void soutTree(TreeNode root) {
//            if(root == null){
//                return;
//            }
//            soutTree(root.left);
//            System.out.println(root.val+" ");
//            soutTree(root.right);
//
//        }
//
//
//    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            if( root == p || root == q ){
                return root;
            }
            TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
            TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
            if( leftRet != null && rightRet != null ){
                return root;
            } else if (leftRet != null) {
                return leftRet;
            } else if ( rightRet != null ) {
                return rightRet;
            }
            return null;
        }
    }







}
